#include<stdio.h>
#include<stdlib.h>
int a;

struct node
{
	int value;
	struct node *next;
};

struct node *start = NULL;
struct node *new_node, *present_node;

void initial()
{
	int i,n;
	printf("Enter no. of nodes: ");
	scanf("%d", &n);
	
	for (i=1;i<=n;i++)
	{
		new_node=(struct node *)malloc(sizeof(struct node));		
	
		printf("Enter element %d: ", i);
		scanf("%d", &new_node->value);
		new_node->next=NULL;

		if(start==NULL)
		{
			start=new_node;
			present_node=new_node;
		}
		else
		{
			present_node->next=new_node;
			present_node=new_node;
		}
	}
		
	struct node *p;
	p=start;
	
	while(p->next!=NULL)
	{
		printf("%d ",p->value);
		p=p->next;
	}

	printf("%d ",p->value);
}	




void index()
{
	int n,a=0,b=0;
	
	printf ("Enter the element to be searched: ");
	scanf ("%d", &n);	
	
	struct node *p;
	p=start;
	
	for (;p != NULL;p = p->next)
	{
		if ((p->value) == n)
		{	
			printf("\nIt is present at the location %d. \n", b);
			a++;
			break;	
		}
		else
		{
			b++;
		}	
	}

	if (a==0)
	{
		printf("\nIt is not present in the list. \n");
	}
}




void count()
{
	int n,a=0;

	printf("Enter the element to be counted: ");
	scanf ("%d", &n);	
	
	struct node *p;
	p=start;
	
	for (;p != NULL;p = p->next)
	{
		if ((p->value) == n)
		{	
			a++;
		}
	}

	printf("\nThe element is present %d times. ", a);
}




void append()
{
	int n,a=0;
	
	new_node=(struct node *)malloc(sizeof(struct node));		
	
	printf("Enter element: ");
	scanf("%d", &new_node->value);
	new_node->next=NULL;

	if(start==NULL)
	{
		start=new_node;
		present_node=new_node;
	}
	else
	{
		present_node->next=new_node;
		present_node=new_node;
	}

	struct node *p;
	p=start;
	
	while(p->next!=NULL)
	{
		printf("%d ",p->value);
		p=p->next;
	}

	printf("%d ",p->value);
}




void extend()
{
	struct node *start1 = NULL;
	struct node *new_node1, *present_node1;
	
	int i,n;
	printf("\nEnter no. of nodes: ");
	scanf("%d", &n);
	
	for (i=1;i<=n;i++)
	{
		new_node1=(struct node *)malloc(sizeof(struct node));		
	
		printf("Enter element %d: ", i);
		scanf("%d", &new_node1->value);
		new_node1->next=NULL;

		if(start1==NULL)
		{
			start1=new_node1;
			present_node1=new_node1;
		}
		else
		{
			present_node1->next=new_node1;
			present_node1=new_node1;
		}
	}
		
	struct node *q;
	q=start1;
	
	printf("\nThe new list is: ");
	
	for (;q != NULL;q = q->next)
	{
		printf("%d ->",q->value);
	}


	struct node *p;
	p=start;
	
	for (;p->next != NULL;p = p->next)
	{
	}
	
	p->next=start1;

	struct node *r;
	r=start;

	printf("\nThe extended list is: "); 
	
	while(r->next!=NULL)
	{
		printf("%d ",r->value);
		r=r->next;
	}

	printf("%d  ",r->value);

}




void insert()
{
	int i,j,m,n;
	int len=0;	

	printf("\nEnter the element to be inserted: ");
	scanf("%d", &n);

	printf("Enter the position where the element should be inserted: ");
	scanf("%d", &m);

	struct node *p;
	p=start;

	for(;p->next!=NULL;p=p->next)
	{
		len++;
	}	
	
	if(m<0 || m>len)
	{
		printf("Position Invalid.\n");
	}
	else
	{
		struct node *new_node2, *p, *q;
		p=start;
		q=start;

		new_node2=(struct node *)malloc(sizeof(struct node));
		new_node2->value=n;
	
		if(m==0)
		{
			new_node2->next=p;
			start=new_node2;
		}
		else
		{
			for(i=0;i<m;i++)
         		{
             			p=start;   
             			p=p->next;
          		}

			new_node2=(struct node *)malloc(sizeof(struct node));
			p->next=new_node2;
			p=new_node2;
			p->next=start;



/*
			for(i=1;i<=m;i++)
			{
				p=p->next;
				new_node2->next=p;
			}
			for(j=1;j<m;j++)
			{			
				q=q->next;
				q->next=new_node2;
			}
*/
		}
	}
	
	struct node *r;
	r=start;
	
	printf("\nThe new list is: "); 
	
	while(r->next!=NULL)
	{
		printf("%d ",r->value);
		r=r->next;
	}

	printf("%d  ",r->value);
	
}






/*
void insert()
{
	




	int n,i=1;	
	
	struct node *new_node2;
	new_node2=(struct node *)malloc(sizeof(struct node));
	
	printf("\nEnter the element to be inserted. ");
	scanf("%d", &new_node2->value);
	
	printf("\nEnter the position where the element should be inserted: ");
	scanf("%d", &n);
	
	struct node *p;
	p=start;
	
	for (;p->next != NULL;p = p->next)
	{
		if (i==n)
		{
			p->next=new_node2;
			//new_node2->next=(p->next)->next;
		}
		i++;
	}

	struct node *r;
	r=start;

	printf("\nThe new list is: "); 
	
	for (;r->next != NULL;r = r->next)
	{
		printf("%d ->",r->value);
	}


}
*/



void delete()
{
	int n;

	printf("Enter the number you want to delete: ");
	scanf("%d", &n);
	
	struct node *p, *q;
	p=start;
      	
	while(p!=NULL)
    	{
       		if(p->value==n)
       		{
        		if(p==start)
           		{
				start=start->next;
				free(p);
           		}
           		else
			{
				q->next=p->next;
				free(p);
         		}
      		}
		else
		{
			q=p;
			p=p->next;
		}
	}

	struct node *r;
	r=start;
	
	while(r->next!=NULL)
	{
		printf("%d ",r->value);
		r=r->next;
	}

	printf("%d ",r->value);

}




void reverse()
{
	struct node *p, *q, *r;
	p=start;
	q=NULL;
	
	while(p!=NULL)
	{
		r=q;
		q=p;
		p=p->next;
		q->next=r;
	}	
	start=q;

	struct node *s;
	s=start;
	
	printf("\nThe reversed list is: ");

	while(s->next!=NULL)
	{
		printf("%d ",s->value);
		s=s->next;
	}

	printf("%d ",s->value);

}




void pop()
{



}



void sort()
{



}



		
void main()
{
	int ans1;
	char ans='y';	
	
	
	while(ans=='y')
	{	
	
		printf("This is python list implementation through linked list.\n");
		printf("1. Initial list\n");
		printf("2. Index\n");
		printf("3. Count\n");
		printf("4. Insert\n");
		printf("5. Append\n");
		printf("6. Sort\n");
		printf("7. Extend\n");
		printf("8. Pop\n");
		printf("9. Remove\n");
		printf("10. Reverse\n");


		printf("Enter your choice: ");
		scanf("%d", &ans1);
	
		if (ans1==1)
		{
			initial();
		}
		else if(ans1==2)
		{
			index();
		}
		else if(ans1==3)
		{
			count();
		}
		else if(ans1==4)
		{
			insert();
		}
		else if(ans1==5)
		{
			append();
		}
		else if(ans1==6)
		{
			sort();
		}
		else if(ans1==7)
		{
			extend();
		}
		else if(ans1==8)
		{
			pop();
		}
		else if(ans1==9)
		{
			delete();
		}
		else if(ans1==10)
		{
			reverse();
		}
		else 
		{
			printf("Invalid selection.");
		}

		fflush(stdin);

		printf("Do you want to continue: ");
		scanf("%s", &ans);

	};
	
	
}
